Thực đơn
Sắp xếp nhanh Mã giả // left là chỉ số của phần tử đầu tiên của mảng // right là chỉ số của phần tử cuối cùng của mảng // số phần tử của mảng = right-left+1function partition(array, 'left', 'right', 'pivotIndex') 1.'pivotValue':= array['pivotIndex'] 2.swap array['pivotIndex'] and array['right'] // Move pivot to end 3.'storeIndex':= 'left' 4.for 'i' from 'left' to 'right'-1 // left ≤ i < right 1.if array['i'] < 'pivotValue' 1.swap array['i'] and array['storeIndex'] 2.'storeIndex':= 'storeIndex' + 1 5.swap array['storeIndex'] and array['right'] // Move pivot to its final place 6.return 'storeIndex'
function quicksort(array, 'left', 'right') // If the list has 2 or more items if 'left' < 'right' // See "Choice of pivot" section below for possible choices choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right' // Get lists of bigger and smaller items and final position of pivot 'pivotNewIndex':= partition(array, 'left', 'right', 'pivotIndex') // Recursively sort elements smaller than the pivot quicksort(array, 'left', 'pivotNewIndex' - 1) // Recursively sort elements at least as big as the pivot quicksort(array, 'pivotNewIndex' + 1, 'right')
#include<stdio.h>#include<conio.h>typedef int keytype;typedef struct{ keytype key;}recordtype;void Swap(recordtype *x, recordtype *y){ recordtype temp; temp = *x; *x = *y; *y = temp;}int FindPivot(recordtype a[],int i, int j){ keytype firstkey; int k; k=i+1; firstkey = a[i].key; while((k<=j)&&(a[k].key==firstkey)) k++; if(k>j) return -1; else if((a[k].key > firstkey)) return k; else return i;}int Partition(recordtype a[],int i, int j, keytype pivot){ int L, R; L=i; R=j; while(L<=R){ while (a[L].key < pivot) L++; while (a[R].key > pivot) R--; if (L < R) Swap(&a[L], &a[R]); } return L;}void QuickSort (recordtype a[], int i, int j){ keytype pivot; int pivotindex, k; pivotindex = FindPivot(a,i, j); if (pivotindex != -1){ pivot = a[pivotindex].key; k = Partition(a, i, j, pivot); QuickSort(a, i, k-1); QuickSort(a, k, j); }}int main(){ int n,i; recordtype a[50]; printf("nhap n: "); scanf("%d",&n); for(i=0;i<n;i++){ printf("nhap phan tu: "); scanf("%d",&a[i].key); } QuickSort(a, 0, n-1); for(i= 0;i<n;i++){ printf(" --- %d",a[i].key); } return 0;}
Nhiều người cho rằng việc khử đệ quy của sắp xếp nhanh thực ra không cần thiết, nó chỉ có tác dụng cho những người mới tiếp cận khoa học máy tính hiểu sâu sắc hơn về khái niệm đệ quy. Bản chất của các giải thuật đệ quy là lưu trữ các tham biến đệ quy vào một ngăn xếp (stack) để lần lượt lấy ra xử lý.
Khi khử đệ quy của giải thuật đệ quy, mỗi lần phân chia danh sách thành 2 danh sách con ta lưu trữ các tham số của danh sách đứng sau vào một ngăn xếp, rồi phân chia tiếp danh sách đứng trước.
Giải thuật đơn giản nhất để khử đệ quy của sắp xếp nhanh như sau:
Procedure QuickSort(a[1..n]) { Var list S, E; Int m:=1 S(m):=1; E(m):= n; While m>0 { k=S(m); l=E(m) m:=m-1; if l<k then { i=Part(k,l); m=m+1; S(m):=i+1 E(m):=l } } }
Ưu điểm của sắp xếp nhanh không đệ quy nằm ở những cải tiến của giải thuật trên đây. Có thể cải tiến theo những hướng sau: Cất vào ngăn xếp danh sách con ít phần tử hơn trong hai danh sách con và đối với các danh sách con có độ dài đủ nhỏ thì dùng một phương pháp sắp xếp sơ cấp (chẳng hạn sắp xếp chèn).
Một phương pháp chia khác là chia danh sách thành 3 danh sách con, lần lượt nhỏ hơn, bằng và lớn hơn phần tử chốt.
function quicksort(a) Var list less, equal, greater if length(a) ≤ 1 return a else select a pivot value pivot from a for each x in a if x < pivot then add x to less if x = pivot then add x to equal if x > pivot then add x to greater return concatenate(quicksort(less), equal, quicksort(greater))
Thực đơn
Sắp xếp nhanh Mã giảLiên quan
Tài liệu tham khảo
WikiPedia: Sắp xếp nhanh